#include <string.h>
#include <stdlib.h>
#include <stdio.h>

#include "sort.h"

RET bubble_sort(void ** data,size_t data_len,data_cmp_fun cmp )
{	
	int i;
	int j;
	int m;
	void *tmp;

	if ((data ==  NULL) || (data_len < 2) || (cmp == NULL)) {
		return RET_PRA;
	}

	for (i=0; i<data_len; i++) {
		m = i;
		for (j=i; j<(data_len-1); j++) {
			if (cmp(data[m],data[j+1]) > 0) {
				m = j+1;
			}
		}
		if (m != i) {
			tmp = data[i];
			data[i] = data[m];
			data[m] = tmp;
		}
	}
	return RET_OK;
}

static RET merge_sort_impl(void** storage, void** array, size_t low, size_t mid, size_t high,data_cmp_fun cmp)
{
	size_t i = low;
	size_t j = low;
	size_t k = mid;

	if ((low + 1) < mid) {
		size_t x = low + ((mid - low) >> 1);
		merge_sort_impl(storage, array, low, x, mid, cmp);
	}
	if ((mid + 1) < high) {
		size_t x = mid + ((high - mid) >> 1);
		merge_sort_impl(storage, array, mid, x, high, cmp);
	}
	while (j < mid && k < high) {
		if (cmp(array[j], array[k]) <= 0) {
		    storage[i++] = array[j++];
		} else {
		    storage[i++] = array[k++];
		}
	}
	while (j < mid) {
		storage[i++] = array[j++];
	}
	while (k < high) {
		storage[i++] = array[k++];
	}
	for (i = low; i < high; i++) {
		array[i] = storage[i];
	}
	return RET_OK;
}

RET merge_sort(void** array, size_t nr, data_cmp_fun cmp)
{
	void** storage = NULL;
	RET ret = RET_OK;

	if ((array ==  NULL) || (nr < 2) || (cmp == NULL)) {
		return RET_PRA;
	}
	if (nr > 1) {
		storage = (void**)malloc(sizeof(void*) * nr);
		if (storage != NULL) {
			ret = merge_sort_impl(storage, array, 0, nr>>1, nr, cmp);
			free(storage);
		}
	}
	return ret;
}

void quick_sort_impl(void** array, size_t left, size_t right, data_cmp_fun cmp)
{
	size_t save_left  = left;
	size_t save_right = right;
	void* x = array[left];
	
	while (left < right) {
		while (cmp(array[right], x) >= 0 && left < right) {
	    		right--;
	    	}
		if (left != right) {
		    array[left] = array[right];
		    left++;
		}
		while (cmp(array[left], x) <= 0 && left < right) {
			left++;
		}
		if (left != right) {
		    array[right] = array[left];
		    right--;
		}
	}

	array[left] = x;
	if (save_left < left) {
	    quick_sort_impl(array, save_left, left-1, cmp);
	}
	if (save_right > left) {
	    quick_sort_impl(array, left+1, save_right, cmp);
	}
	return;
}
RET quick_sort(void** array, size_t nr, data_cmp_fun cmp)
{
    RET  ret = RET_OK;
	
    if(nr > 1) {
        quick_sort_impl(array, 0, nr - 1, cmp);
    }
    return ret;
}


RET  half_seek_impl(void **data, int low, int high,void *seek_data,data_cmp_fun cmp,void ** ret_data)
{
	int ret ;
	int mid ;
	
	if (data == NULL  || cmp == NULL) {
		return RET_PRA;
	}
	
	if (low>= high && (cmp(data[low],seek_data)) != 0) {
		return RET_NONE;
	}
	mid = (low + high) / 2; 
	ret = cmp(data[mid],seek_data);

	if (ret == 0) {
		*ret_data = data[mid];
		return RET_OK;
	} else if (ret > 0) {
		high = mid -1;
	} else {
		low = mid + 1;
	}
	return   half_seek_impl(data,  low,  high,seek_data, cmp,ret_data);
}

RET  half_seek(void ** data,size_t data_len,data_cmp_fun cmp,void * seek_data,void ** ret_data)
{
	if ((data ==  NULL) || (data_len < 1) || (ret_data == NULL) ||\
		(cmp == NULL) ) {
		return RET_PRA;
	}
	return half_seek_impl(data,  0,  data_len-1,seek_data, cmp,ret_data);
}

void  merge(int* data,int l,int m,int r,data_cmp_fun cmp)
{
	int left[m-l+1];
	int right[r-m];
	int i;
	int ll = 0;
	int rr = 0;
	int len = r-l+1;
	int in = l;
	
	memcpy(left,data+l,(m-l+1)*sizeof(int));
	memcpy(right,data+(m+1),(r-m)*sizeof(int));
	for (i=0; i<len; i++) {
		if (cmp((int *)left[ll],(int *)right[rr]) > 0) {
			data[in] = left[ll];
			ll++;
		} else {
			data[in] = right[rr];
			rr++;
		}
		in++;
		if ((ll == (m-l+1)) &&  (rr != (r-m))) {
			memcpy(data+in,right+rr,(r-m-rr)*sizeof(int));
			break;
		} else if ((ll != (m-l+1)) &&  (rr == (r-m))) {
			memcpy(data+in,left+ll,(m-l+1-ll)*sizeof(int));
			break;
		}
	}
}

void  merge_sort_yxl(int* data,int l,int r,data_cmp_fun cmp)
{
	int mid = 0;
	
	if (l <  r) {
		mid = (l+r)>>1;
		merge_sort_yxl(data,l,mid,cmp);
		merge_sort_yxl(data,mid+1,r,cmp);
		merge(data,l,mid,r,cmp);
	} 
}


